0464. 我能赢吗【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 状压 DP + 记忆化搜索

1. 📝 题目描述

• leetcode

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true，否则返回 false。假设两位玩家游戏时都表现 最佳。

---

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2：

输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3：

输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

---

提示：

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

2. 🎯 s.1 - 状压 DP + 记忆化搜索

c

int* memo;

bool dfs(int maxN, int used, int remain) {
    if (memo[used] != -1) return memo[used];
    for (int i = 1; i <= maxN; i++) {
        if (used & (1 << i)) continue;
        if (i >= remain || !dfs(maxN, used | (1 << i), remain - i)) {
            memo[used] = 1;
            return true;
        }
    }
    memo[used] = 0;
    return false;
}

bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if ((long long)maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
    if (desiredTotal <= 0) return true;
    int size = 1 << (maxChoosableInteger + 1);
    memo = (int*)malloc(sizeof(int) * size);
    memset(memo, -1, sizeof(int) * size);
    bool res = dfs(maxChoosableInteger, 0, desiredTotal);
    free(memo);
    return res;
}

js

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
  if ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2 < desiredTotal)
    return false
  if (desiredTotal <= 0) return true
  const memo = new Map()
  const dfs = (used, remain) => {
    if (memo.has(used)) return memo.get(used)
    for (let i = 1; i <= maxChoosableInteger; i++) {
      if (used & (1 << i)) continue
      if (i >= remain || !dfs(used | (1 << i), remain - i)) {
        memo.set(used, true)
        return true
      }
    }
    memo.set(used, false)
    return false
  }
  return dfs(0, desiredTotal)
}

py

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:
            return False
        if desiredTotal <= 0:
            return True
        @cache
        def dfs(used, remain):
            for i in range(1, maxChoosableInteger + 1):
                if used & (1 << i):
                    continue
                if i >= remain or not dfs(used | (1 << i), remain - i):
                    return True
            return False
        return dfs(0, desiredTotal)

• 时间复杂度：$O(2^n\times n)$，其中 $n$ = maxChoosableInteger
• 空间复杂度：$O(2^n)$

算法思路：

• 用位掩码表示已选整数集合
• DFS 遍历每个可选整数，若能直接达到目标或者对手必败，则当前玩家胜
• 记忆化缓存已搜索状态